Merge Sort マージソート
Sorting ソート 整列アルゴリズム Algorithmsの一種
分解し再帰的に解く分割統治法
配列 Arrayを半分にわけて、それぞれをSorting ソート 整列し、２つをマージすることを繰り返す
特徴
O(n log n)
入力長が増えても高速
データの出現順序による時間計算量 time complexityの変化小
外部ソート(メモリ食う)
空間計算量 space complexity n
マージ操作のための余分メモリ必要
安定性 Algorithms
標語
マージソートちゃんマジソート
利点
O(n log n)
安定性 Algorithms
→しかし、Quicksort クイックソートに劣る
したがって、用途なさそう
table:mergeSort
Name Best Average Worst Memory Stable Comments
Merge sort O(n log n) O(n log n) O(n log n) n Yes
GitHub.iconmy-javascript-algorithms/Sorting/MergeSort at master · KiichiSugihara/my-javascript-algorithms
参考
Merge Sort in JavaScript | メモログ